package _220316;

/**
 * @author ShadowLim
 * @create 2022-03-16-9:51
 */
public class _最大乘积 {
    /**
     *  tags:不含重复数字的全排列
     */
    static int[] a = new int[9];
    static int max;
    static boolean[] vis = new boolean[10];

    public static void main(String[] args) {
        dfs(0);
        System.out.println(max);
    }

    /**
     * 全排列模板生成不带重复元素
     * @param k
     */
    private static void dfs(int k) {
        if (k == 9) {
            for (int i = 0; i < 8; i++) {
                int t = getNum(i);
                if (check(t) && t > max) {
                    max = t;
                }
            }
            return;
        }
        // 尝试将没用过的数字放到当前位置
        for (int i = 1; i < 10; i++) {
            if (!vis[i]) {
                vis[i] = true;
                a[k] = i;
                dfs(k + 1);
                vis[i] = false;
            }
        }
    }

    /**
     *  返回两个数的乘积
     * @param pos 乘号插入的位置
     * @return
     */
    private static int getNum(int pos) {
        int t1 = 0, t2 = 0;
        // 第一个乘数
        for (int i = 0; i <= pos; i++) {
            t1 = t1 * 10 + a[i];
        }
        // 第二个乘数
        for (int i = pos + 1; i < 9; i++) {
            t2 = t2 * 10 + a[i];
        }
        return t1 * t2;
    }

    /**
     * 判断乘积是否只包含1~9这9个数字且每个数字只出现一次
     * @param num
     * @return
     */
    private static boolean check(int num) {
        if (num > 1e10) {
            return false;
        }
        boolean[] v = new boolean[10];
        while (num != 0) {
            int t = num % 10;
            if (t == 0) {   // 余数为0 说明num最低位置的数字为0 不符合「乘积只包含1~9这9个数字」的条件
                return false;
            }
            // 判断乘每个位置上的数字是否只出现一次
            if (v[t]) { // 当前位置的数字已经出现过 直接false
                return false;
            }
            v[t] = true;
            num /= 10;
        }
        return true;
    }
}
